[WIP] 36. Valid Sudoku

Question

Determine if a 9 x 9 Sudoku board is valid. Only the filled cells need to be validated according to the following rules:

Each row must contain the digits 1-9 without repetition. Each column must contain the digits 1-9 without repetition. Each of the nine 3 x 3 sub-boxes of the grid must contain the digits 1-9 without repetition.

Note:

• A Sudoku board (partially filled) could be valid but is not necessarily solvable.
• Only the filled cells need to be validated according to the mentioned rules.

Example 1:

Input: board = 
[["5","3",".",".","7",".",".",".","."]
,["6",".",".","1","9","5",".",".","."]
,[".","9","8",".",".",".",".","6","."]
,["8",".",".",".","6",".",".",".","3"]
,["4",".",".","8",".","3",".",".","1"]
,["7",".",".",".","2",".",".",".","6"]
,[".","6",".",".",".",".","2","8","."]
,[".",".",".","4","1","9",".",".","5"]
,[".",".",".",".","8",".",".","7","9"]]
Output: true

Example 2:

Input: board = 
[["8","3",".",".","7",".",".",".","."]
,["6",".",".","1","9","5",".",".","."]
,[".","9","8",".",".",".",".","6","."]
,["8",".",".",".","6",".",".",".","3"]
,["4",".",".","8",".","3",".",".","1"]
,["7",".",".",".","2",".",".",".","6"]
,[".","6",".",".",".",".","2","8","."]
,[".",".",".","4","1","9",".",".","5"]
,[".",".",".",".","8",".",".","7","9"]]
Output: false
Explanation: Same as Example 1, except with the 5 in the top left corner being modified to 8. Since there are two 8's in the top left 3x3 sub-box, it is invalid.

Constraints:

• board.length == 9
• board[i].length == 9
• board[i][j] is a digit 1-9 or '.'.

---

Approach

Solution

class Solution {
public:
    bool isValidSudoku(vector<vector<char>>& board) {
        unordered_map<char,int> cells;
        
        //check rows
        for(int i = 0; i < 9; i++){
            for(int j = 0; j < 9; j++){
                if(board[i][j] != '.') cells[board[i][j]]++;
                if(cells[board[i][j]] > 1) return false;
            }
            cells.clear();
        }
        
        //check cols
        for(int i = 0; i < 9; i++){
            for(int j = 0; j < 9; j++){
                if(board[j][i] != '.') cells[board[j][i]]++;
                if(cells[board[j][i]] > 1) return false;
            }
            cells.clear();
        }
        
        vector<vector<pair<int,int>>> cell;
        vector<pair<int,int>> cell1 = {{0,0},{3,3}};
        vector<pair<int,int>> cell2 = {{0,3},{3,6}};
        vector<pair<int,int>> cell3 = {{0,6},{3,9}};
        vector<pair<int,int>> cell4 = {{3,0},{6,3}};
        vector<pair<int,int>> cell5 = {{3,3},{6,6}};
        vector<pair<int,int>> cell6 = {{3,6},{6,9}};
        vector<pair<int,int>> cell7 = {{6,0},{9,3}};
        vector<pair<int,int>> cell8 = {{6,3},{9,6}};
        vector<pair<int,int>> cell9 = {{6,6},{9,9}};

        cell.push_back(cell1);
        cell.push_back(cell2);
        cell.push_back(cell3);
        cell.push_back(cell4);
        cell.push_back(cell5);
        cell.push_back(cell6);
        cell.push_back(cell7);
        cell.push_back(cell8);
        cell.push_back(cell9);

        //check 3x3
        int itr = 0;

        while(itr < cell.size()){
            int rStart = cell[itr][0].first;
            int cStart = cell[itr][0].second;
            int w = cell[itr][1].first;
            int h = cell[itr][1].second;
            cout << "rStart: " << rStart << " cStart: " << cStart << " w: " << w << " h: " << h << endl;
            
            for(int i = rStart; i < w; i++){
                for(int j = cStart; j < h; j++){
                    if(board[i][j] != '.'){
                        cout << "checking: " << board[i][j] << " at" << i<< j << endl;
                        cells[board[i][j]]++;
                    } 
                    if(cells[board[i][j]] > 1){
                        cout << "3 x 3 false: " << i << j << " count: " << cells[board[i][j]]<< endl;
                        return false;
                    } 
                }
            }
            cells.clear();
            itr++;
        }
        return true;
    }
};